package tree;

/**
 * @Author leecho
 * @Date: 2021/10/28 16:18
 * @Version 1.0
 */

public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();

        for (int i : arr) {
            binarySortTree.addNodeToTree(new BinarySortTreeNode(i));
        }

        binarySortTree.infixListTree();
        System.out.println();

        BinarySortTreeNode target = binarySortTree.getTarget(1);
        System.out.println(target);

        BinarySortTreeNode sortTreeNode = binarySortTree.searchTargetParent(1);
        System.out.println(sortTreeNode);

        System.out.println("=============");

        binarySortTree.deleteNode(2);

        binarySortTree.infixListTree();

    }
}

class BinarySortTree{
    BinarySortTreeNode root;

    public void addNodeToTree(BinarySortTreeNode node){
        if (root == null)
            root = node;
        else {
            root.addNode(node);
        }
    }

    public void infixListTree(){
        if (root == null)
            System.out.println("空树，无法遍历");
        else
            root.infixList();
    }

    public BinarySortTreeNode getTarget(int val){
        if (root == null)
            return null;
        else
          return root.getTargetNode(val);
    }

    public BinarySortTreeNode searchTargetParent(int val){
        if (root == null)
            return null;
        else
            return root.searchTargetParent(val);
    }

    public void deleteNode(int val){
        if (root == null)
            System.out.println("空树，无法删除节点");
        else {
            BinarySortTreeNode node = root.deleteNode(val);
            root = node;
        }
    }
}

/*
* 思路
* - 采用递归的方法添加
* - 删除节点
*       - 找到要删除的目标结点，然后再找到要删除结点的父节点
*       - 设置删除规则
* */
class BinarySortTreeNode{
    int no;
    BinarySortTreeNode left;
    BinarySortTreeNode right;

    public BinarySortTreeNode(int no) {
        this.no = no;
    }

    public void addNode(BinarySortTreeNode node){
        if (this.no > node.no){
            if (this.left == null){
                this.left = node;
            } else {
                this.left.addNode(node);
            }
        } else {
            if (this.right == null){
                this.right = node;
            } else {
                this.right.addNode(node);
            }
        }
    }

    public void infixList(){
        System.out.printf("%4d",this.no);
        if (this.left != null)
            this.left.infixList();
        if (this.right != null)
            this.right.infixList();
    }

    public BinarySortTreeNode getTargetNode(int val){
        if (this.no == val)
            return this;
        else if (val < this.no){
            if (this.left != null){
              return this.left.getTargetNode(val);
            }
        } else {
            if (this.right != null){
                return this.right.getTargetNode(val);
            }
        }
        return null;
    }

    public BinarySortTreeNode searchTargetParent(int val){
        if (this.left != null && this.left.no == val){
            return this;
        }
        if (this.right != null && this.right.no == val){
            return this;
        }
        if (this.left != null){
            return this.left.searchTargetParent(val);
        }
        if (this.right != null){
            return this.right.searchTargetParent(val);
        }
        return null;
    }

    public BinarySortTreeNode deleteNode(int val){
        BinarySortTreeNode targetNode = getTargetNode(val);
        BinarySortTreeNode targetParent = searchTargetParent(val);
        boolean flag = true;

        if ( targetParent == null){
            targetNode = null;
            flag =false;
            return null;
        }

        while (flag){
            if (targetNode.left == null && targetNode.right == null && targetNode.no < targetParent.no){
                targetParent.left = null;
            } else if (targetNode.left == null && targetNode.right == null && targetNode.no > targetParent.no){
                targetParent.right = null;
            } else if (targetNode.no < targetParent.no){
                targetParent.left = targetNode.left;
                targetNode.left.right = targetNode.right;
            } else if (targetNode.no > targetParent.no){
                targetParent.right = targetNode.right;
                targetNode.right.left = targetNode.left;
            } else if (targetNode.right == null && targetNode.left !=null){
                targetParent.left = targetNode.left;
            } else if (targetNode.right != null && targetNode.left ==null){
                targetParent.right = targetNode.right;
            }
            flag = false;
        }
        return this;
    }



    @Override
    public String toString() {
        return "BinarySortTreeNode{" +
                "no=" + no +
                '}';
    }
}